/*
 * @Author: 缄默
 * @Date: 2022-03-09 18:40:01
 * @LastEditors: 缄默
 * @LastEditTime: 2022-03-09 19:09:38
 */

//跳跃游戏

#include <iostream>
#include <vector>

using namespace std;

int minJump(vector<int> & arr);

int main() {
    vector<int> arr ({3, 2, 3, 1, 1, 4});
    cout << minJump(arr) << endl;
    return 0;
}

int minJump(vector<int> & arr) {
    if (arr.size() <= 1) return 0;
    int min = 0;
    int next = 0;
    int cur = 0;
    for (int i  = 0; i < arr.size(); i++) {
        //当前范围内的比较完毕，就把next赋值给cur 及新的范围 并且步数加1
        if (cur < i) {
            min++;
            cur = next;
        }
        //在cur的范围内最大的next；
        next = next < i + arr[i] ? i + arr[i] : next;
    }
    return min;
}
